﻿using System;
using System.Linq;
using Algoritmia.DataStructures.Lists;
using Algoritmia.DataStructures.Maps;
using Algoritmia.DataStructures.Trees;
using Algoritmia.Utils;

namespace Algoritmia.Problems.Parsing
{
    public class CYKParser : IParser
    {
        private readonly IMap<string, IList<string>> _productions;
        private readonly string _S;
        private readonly Func<IMap<string, IList<string>>,int, IMap<Tuple<int, int, string>, bool>> _createMap;
        private readonly Func<IMap<string, IList<string>>, int, IMap<Tuple<int, int, string>, Tuple<int, string, string>>> _createBackpointersMap;

        public CYKParser(IMap<string,IList<string>> productions,
                         string S, 
                         Func<IMap<string,IList<string>>,int,IMap<Tuple<int,int,string>,bool>> createMap = null,
                         Func<IMap<string, IList<string>>, int, IMap<Tuple<int, int, string>, Tuple<int, string, string>>> createBackpointersMap = null)
        {
            _productions = productions;
            _S = S;
            _createMap = createMap ?? ((P, n) => AlgoritmiaFactory.Maps<Tuple<int,int,string>,bool>.Default);
            _createBackpointersMap = createBackpointersMap ??
                                     ((P, n) => AlgoritmiaFactory.Maps<Tuple<int, int, string>, Tuple<int, string, string>>.Default);
        }

        public class ASTTree : BinaryTree
        {
            private readonly string _noTerminal;
            private readonly string _value;
            public bool IsTerminal { get; private set; }

            public ASTTree(string noTerminal, ASTTree LHS, ASTTree RHS)
                : base(null,LHS,RHS)
            {
                _noTerminal = noTerminal;
                IsTerminal = false;
            }

            public ASTTree(string terminal)
            {
                _value = terminal;
                IsTerminal = true;
            }

            public string NoTerminal
            {
                get
                {
                    if (!IsTerminal)
                    {
                        return _noTerminal;
                    }
                    throw new InvalidOperationException("Is not possible to get the NoTerminal property of a Terminal node");
                }
            }

            public string Value
            {
                get
                {
                    if (IsTerminal)
                    {
                        return _value;
                    }
                    throw new InvalidOperationException("Is not possible to get the Value property of a NoTerminal node");
                }
            }

            public override string ToString()
            {
                if ( IsTerminal )
                {
                    return "'" + _value + "'";
                }
                return String.Format("['{0}', {1}, {2}]", _noTerminal, Left, Right);
            }

        }

        #region Implementation of IParser

        public bool Accepts(string x)
        {
            int n = x.Length;
            var Pi = _createMap(_productions, n);
            for(int i = 0; i< n; i++)
            {
                foreach(var A in _productions.Keys())
                {
                    Pi[new Tuple<int, int, string>(i, i, A)] =
                        _productions[A].Where(s => s.Length == 1).Any(s => x[i] == s[0]);
                }
            }
            for(int k = 1; k < n; k++)
            {
                for(int i = 0; i < n-k; i++)
                {
                    foreach(var A in _productions.Keys())
                    {
                        Pi[new Tuple<int, int, string>(i, i + k, A)] = (from j in Enumerable.Range(i, k)
                                                                        from right in _productions[A]
                                                                        where right.Length == 2
                                                                        select Pi[new Tuple<int, int, string>(i, j, right.Substring(0, 1))] &&
                                                                               Pi[new Tuple<int, int, string>(j + 1, i + k, right.Substring(1, 1))]).Any(e => e);
                    }
                }
            }
            return Pi[new Tuple<int, int, string>(0, n - 1, _S)];
        }

        #endregion

        public ASTTree ParseTree(string x)
        {
            int n = x.Length;
            var Pi = _createMap(_productions, n);
            var back = _createBackpointersMap(_productions, n);
            for (int i = 0; i < n; i++)
            {
                foreach (var A in _productions.Keys())
                {
                    var tple = new Tuple<int, int, string>(i, i, A);
                    Pi[tple] = false;
                    foreach(var p in _productions[A])
                    {
                        if ( p.Length == 1 && x[i] == p[0])
                        {
                            Pi[tple] = true;
                            back[tple] = new Tuple<int, string, string>(-1,x.Substring(i,1),"");
                            break;
                        }
                    }
                   
                }
            }
            for (int k = 1; k < n; k++)
            {
                for (int i = 0; i < n - k; i++)
                {
                    foreach (var A in _productions.Keys())
                    {
                        var tple = new Tuple<int, int, string>(i, i + k, A);
                        Pi[tple] = false;
                        foreach(var right in _productions[A])
                        {
                            if ( right.Length == 2)
                            {
                                for(int j = i; j < i+k; j++)
                                {
                                     if ( Pi[new Tuple<int, int, string>(i, j, right.Substring(0, 1))] &&
                                             Pi[new Tuple<int, int, string>(j + 1, i + k, right.Substring(1, 1))])
                                     {
                                         Pi[tple] = true;
                                         back[tple] = new Tuple<int, string, string>(j,right.Substring(0,1),right.Substring(1,1));
                                         break;
                                     }
                                }
                            }
                        }
                    }
                }
            }

            Func<int, int, string, ASTTree> backtrace = null;
            backtrace = (i, k, A) =>
                            {
                                var tp = back[new Tuple<int, int, string>(i, k, A)];
                                if (tp.Item1 == -1)
                                {
                                    return new ASTTree(tp.Item2);
                                }
                                var j = tp.Item1;
                                var NT1 = tp.Item2;
                                var NT2 = tp.Item3;
                                return new ASTTree(A, backtrace(i, j, NT1), backtrace(j + 1, k, NT2));
                            };
            return backtrace(0, n - 1, _S);
        }
    }
}
